package SwordOffer;

public class Sword_Offer_04 {

    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix.length<1) {
            return false;
        }
        // rowIndex 当前遍历到哪一行，matrix[rowIndex][0 ～ rowLastIndex]的值都<=target，rowLastIndex + 1 == 越界 || matrix[rowIndex][rowLastIndex + 1] > 0
        int rowIndex = 0, rowLastIndex = matrix[0].length - 1;
        while (rowIndex < matrix.length) {
            // 寻找第rowIndex行的rowLastIndex值
            int end = firstGtIndex(matrix[rowIndex], target, 0, rowLastIndex);
            System.out.println("row = " + (rowIndex + 1) + "; endIndex = " + (end + 1));
            if (end < 0) {
                // 如果这一行的第一个数字就比target大，那整个数组就不存在target
                return false;
            } else if (matrix[rowIndex][end] == target) {
                return true;
            } else {
                rowLastIndex = end;
            }
            rowIndex++;
        }
        return false;
    }

    private int firstGtIndex(int[] rows, int target, int begin, int end) {
        while (begin < end) {
            int middle = (begin + end + 1) / 2;
            if (rows[middle] == target) {
                return middle;
            } else if (rows[middle] < target) {
                begin = middle;
            } else {
                end = middle - 1;
            }
        }
        return end;
    }

    public static void main(String[] args) {
        Sword_Offer_04 model = new Sword_Offer_04();
        System.out.println(model.findNumberIn2DArray(new int[][]{
            {1,   4,  7, 11, 15},
            {2,   5,  8, 12, 19},
            {3,   6,  9, 16, 22},
            {10, 13, 14, 17, 24},
            {18, 21, 23, 26, 30}
        }, 20));
    }
}
